package com.jc.projecteuler.january;

/**
 * If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
 * <p>
 * Find the sum of all the multiples of 3 or 5 below 1000.
 */
public class Problem1 {

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        int below = 1000000000;
        System.out.println(sumMultiples35Below(below));
        System.out.println("uses "+(System.currentTimeMillis()-begin)+"ms");

        long begin2 = System.currentTimeMillis();
        System.out.println(sumMultiples35BelowOptimized(below));
        System.out.println("uses "+(System.currentTimeMillis()-begin2)+"ms");


    }/**output:
     * 233333333166666668
     * uses 2190ms
     * 233333334166666668
     * uses 0ms
     */

    /**
     * 算出小于below的自然数，且此自然数是3或5的倍数，然后再将这些符合条件的自然数累加
     * @param below
     * @return
     */
    private static long sumMultiples35Below(long below) {
        long sum = 0;
        //i is natural number below 10
        for (int i = 0; i < below; i++) {
            if (i == 0) {
                continue;
            }

            if (i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
        }
        return sum;
    }


    /***
     * 优化版
     * @param below
     * @return
     */
    private static long sumMultiples35BelowOptimized(int below){
        return sumDivisibleBy(below,3)+sumDivisibleBy(below,5)-sumDivisibleBy(below,15);
    }

    /***
     * 优化版
     * @param below
     * @param n
     * @return
     */
    private static long sumDivisibleBy(int below,int n){
        long p = below/n;
        return n*((p+1)*p)/2;
    }
}
